The growth of backbone bandwidths from 10 Mbps to 10 Gbps has surpassed the growth of microprocessor performance in mainstream servers and computers. With the rapid growth of network bandwidth, the traffic load over a processing engine (PE) becomes much heavier, and a single PE can't sustain such high traffic load in general. As used herein, the term “processing engine” refers to any entity that is capable of processing traffic flows in the network.
One feasible solution for processing large amount of network traffic is to divide an overall traffic into several subsets of manageable size, thereby reducing the traffic load on a single PE. Parallel architecture has been developed for dispatching and processing packets of a network traffic flow. It will be appreciated that essential to such solution is the load balancing when scheduling traffic flow.
Referring to FIG. 1, a block diagram of high-level architecture for load balancing in scheduling a network traffic flow is illustrated. As shown, there is a load balancer 102 which is responsible for selecting, based on certain policies, a target PE for each packet in an incoming traffic flow. A packet scheduler 104 coupled to the load balancer 102 may be used to dispatch the packets to one of multiple available PEs in accordance with the selection made by the load balancer 102. It will be understood that the selection of target PE is of importance for the scheduling of traffic flows.
Effective load balancing is largely dependent on the policy for dispatching packets of traffic flows over multiple PEs. In general, a load balancing policy shall be as fair as possible. That is, the packets in a traffic flow shall be dispatched evenly, so as to avoid the situation where some PEs are heavily loaded while others are idle. Additionally, due to the varying natures of packets, the time and resource required to process individual packets may be different. Therefore, the dynamic capability or workload of each PE shall be taken into consideration when scheduling the traffic flows. Further, for many content oriented network applications, it is required that all the packets belonging to the same flow are dispatched to and processed by the same PE. Considering network security applications for example, many network activities hide their behavior feature so that the detection technology based on independent packet can't identify them. If all packets of a flow are not scheduled to an identical PE, the performance and accuracy may be reduced.
There have been several existing load balancing solutions. For example, round robin and randomization are typical examples of simple load balancing policies. However, such simple policies, which operate at packet level, cannot preserve packet order within individual flows, and cannot be used in content oriented applications. As an alternative, hash based solutions are widely used for load balancing in many network devices. Hash algorithms generally operate at flow level, and therefore could ensure that packets from a same flow are dispatched to an identical PE. Unfortunately, a hash algorithm alone is not able to balance workload when facing highly skewed flow size distributions in the network such as the Internet. Furthermore, performing load balancing by simply hashing the incoming packets does not consider the workload of each PE.
Another kind of load balancing solutions is on the basis of flow. In such solutions, each flow's scheduling status is recorded in a so-called flow table, such that the packets from a single flow can be dispatched to one PE. These solutions show a good performance in low bandwidth networks (no bigger than 100 Mbps). However, for high bandwidth networks (such as 10 Gbps) where there are millions of concurrent traffic flows, flow based solutions generally result in a very large flow table. A large flow table consumes not only lots of memory resources but also substantial searching time to determine which PE a packet shall be dispatched to when a new packet arrives.
In view of the foregoing problems, there is a need to provide an improved solution for load balancing in scheduling network traffic flows with respect to a plurality of PEs so as to overcome the above defects.